{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Most Frequent Subtree Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findFrequentTreeSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #出现次数最多的子树元素和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉树的根结点&nbsp;<code>root</code>&nbsp;，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。</p>\n",
    "\n",
    "<p>一个结点的&nbsp;<strong>「子树元素和」</strong>&nbsp;定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/24/freq1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [5,2,-3]\n",
    "<strong>输出:</strong> [2,-3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/24/freq2-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [5,2,-5]\n",
    "<b>输出:</b> [2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数在&nbsp;<code>[1, 10<sup>4</sup>]</code>&nbsp;范围内</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [most-frequent-subtree-sum](https://leetcode.cn/problems/most-frequent-subtree-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [most-frequent-subtree-sum](https://leetcode.cn/problems/most-frequent-subtree-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,-3]', '[5,2,-5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def xiugai(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            root.val = root.val + xiugai(root.left) + xiugai(root.right)\n",
    "            if root.val in dic:\n",
    "                dic[root.val] += 1\n",
    "            else:\n",
    "                dic[root.val] = 1\n",
    "            return root.val\n",
    "        \n",
    "        dic = {}\n",
    "        xiugai(root)\n",
    "        \n",
    "        m = 0\n",
    "        for k, v in dic.items():\n",
    "            if v > m:\n",
    "                m = v\n",
    "        ans = []\n",
    "        for k, v in dic.items():\n",
    "            if v == m:\n",
    "                ans.append(k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # corner case\n",
    "        if not root.left and not root.right:\n",
    "            return [root.val]\n",
    "\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l_sum = dfs(root.left)\n",
    "            r_sum = dfs(root.right)\n",
    "            sub_sum = l_sum + r_sum + root.val\n",
    "            dic[sub_sum] += 1\n",
    "            return sub_sum\n",
    "        \n",
    "        dfs(root)\n",
    "        # at this time, the dic has been converted to list\n",
    "        sum_arr = sorted(dic.items(), key = lambda x: x[1], reverse = True)\n",
    "        res = [sum_arr[0][0]]\n",
    "        for i in range(1, len(sum_arr)):\n",
    "            if sum_arr[i][1] == sum_arr[0][1]:\n",
    "                res.append(sum_arr[i][0])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:\n",
    "        def helper(node:TreeNode) -> int:\n",
    "            #nonlocal dic\n",
    "            if node is None: return 0\n",
    "            left = helper(node.left)\n",
    "            right = helper(node.right)\n",
    "            sums = node.val + left + right\n",
    "            dic[sums] += 1\n",
    "            return sums\n",
    "        dic = defaultdict(int)\n",
    "        helper(root)\n",
    "        dic = dict(sorted(dic.items(),key = lambda x:-x[1]))\n",
    "        maxs = 0\n",
    "        ans = []\n",
    "        for key,val in dic.items():\n",
    "            if val >= maxs: \n",
    "                ans.append(key)\n",
    "                maxs = val\n",
    "            else:\n",
    "                return ans\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return\n",
    "\n",
    "        self.sum += head.val\n",
    "\n",
    "        self.process(head.left)\n",
    "        self.process(head.right)\n",
    "\n",
    "    def findFrequentTreeSum(self, root):\n",
    "        queue = []\n",
    "        self.sum = 0\n",
    "        self.chart = {}\n",
    "\n",
    "        queue.append(root)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "\n",
    "            self.process(node)\n",
    "            if self.sum in self.chart:\n",
    "                self.chart[self.sum] += 1\n",
    "            else:\n",
    "                self.chart[self.sum] = 1\n",
    "            self.sum = 0\n",
    "\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "\n",
    "        print(self.chart)\n",
    "        maxn = []\n",
    "        for key, value in self.chart.items():\n",
    "            if not maxn:\n",
    "                maxn.append([key, value])\n",
    "            elif value > maxn[0][1]:\n",
    "                maxn.clear()\n",
    "                maxn.append([key, value])\n",
    "            elif value == maxn[0][1]:\n",
    "                maxn.append([key, value])\n",
    "        \n",
    "        for i in maxn:\n",
    "            queue.append(i[0])\n",
    "        \n",
    "        return queue\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> list[int]:\n",
    "        ans_count = dict()\n",
    "\n",
    "        def dfs(node: TreeNode | None) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ans = node.val\n",
    "            if node.left is not None:\n",
    "                ans += dfs(node.left)\n",
    "            if node.right is not None:\n",
    "                ans += dfs(node.right)\n",
    "            if ans not in ans_count:\n",
    "                ans_count[ans] = 1\n",
    "            else:\n",
    "                ans_count[ans] += 1\n",
    "            return ans\n",
    "\n",
    "        dfs(root)\n",
    "        _max = max(ans_count.values())\n",
    "        return [key for key in ans_count.keys() if ans_count[key] == _max]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "        val = {}\n",
    "        def hourec(root):\n",
    "            if not root:\n",
    "                return\n",
    "            left = hourec(root.left) if root.left else 0\n",
    "            right = hourec(root.right) if root.right else 0\n",
    "            tmp = root.val + left + right\n",
    "            val[tmp] = val.get(tmp, 0) + 1\n",
    "            return tmp\n",
    "        hourec(root)\n",
    "        va = sorted(val.items(), key = lambda x:(-x[1], x[0]))\n",
    "        ini = va[0][1]\n",
    "        res = []\n",
    "        print(va)\n",
    "        for v in va:\n",
    "            if v[1] == ini:\n",
    "                res.append(v[0])\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def recur(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            valSum = node.val + recur(node.left) + recur(node.right)\n",
    "            freqDict[valSum] += 1\n",
    "            if freqDict[valSum] > self.maxCount:\n",
    "                self.maxCount += 1\n",
    "                self.ans = [valSum]\n",
    "            elif freqDict[valSum] == self.maxCount:\n",
    "                self.ans.append(valSum)\n",
    "            return valSum\n",
    "\n",
    "        self.maxCount = 0\n",
    "        self.ans = []\n",
    "        freqDict = defaultdict(int)\n",
    "        recur(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> list[int]:\n",
    "        ans_count = dict()\n",
    "\n",
    "        def dfs(node: TreeNode | None) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ans = node.val\n",
    "            if node.left is not None:\n",
    "                ans += dfs(node.left)\n",
    "            if node.right is not None:\n",
    "                ans += dfs(node.right)\n",
    "            if ans not in ans_count:\n",
    "                ans_count[ans] = 1\n",
    "            else:\n",
    "                ans_count[ans] += 1\n",
    "            return ans\n",
    "\n",
    "        dfs(root)\n",
    "        _max = max(ans_count.values())\n",
    "        return [key for key in ans_count.keys() if ans_count[key] == _max]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.hashmap=dict()\n",
    "        self.search(root)\n",
    "        key=list(self.hashmap.keys())\n",
    "        key.sort(key=lambda x:self.hashmap[x])\n",
    "        maxnum=self.hashmap[key[-1]]\n",
    "        res=[]\n",
    "        for i in range(len(key)-1, -1, -1):\n",
    "            if self.hashmap[key[i]]==maxnum:\n",
    "                res.append(key[i])\n",
    "        return res\n",
    "\n",
    "    def search(self, node):\n",
    "        if not node:\n",
    "            return 0\n",
    "        left = self.search(node.left)\n",
    "        right = self.search(node.right)\n",
    "        res=node.val+left+right\n",
    "        if res in self.hashmap:\n",
    "            self.hashmap[res]+=1\n",
    "        else:\n",
    "            self.hashmap[res]=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def myfun(self,node):\n",
    "        if node == None:\n",
    "            return 0\n",
    "        if node.left == None and node.right == None:\n",
    "            if node.val in self.maps.keys():\n",
    "                self.maps[node.val] += 1\n",
    "            else:\n",
    "                self.maps[node.val] = 1\n",
    "            if self.maps[node.val] > self.maxCount:\n",
    "                self.maxCount = self.maps[node.val]\n",
    "            return node.val\n",
    "        s = node.val + self.myfun(node.left) + self.myfun(node.right)\n",
    "        if s in self.maps.keys():\n",
    "            self.maps[s] += 1\n",
    "        else:\n",
    "            self.maps[s] = 1\n",
    "        if self.maps[s] > self.maxCount:\n",
    "            self.maxCount = self.maps[s]\n",
    "        return s\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.maps = {}\n",
    "        self.maxCount = 0\n",
    "        result = []\n",
    "        self.myfun(root)\n",
    "        for key in self.maps.keys():\n",
    "            if self.maps[key] == self.maxCount:\n",
    "                result.append(key)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> list[int]:\n",
    "        ans_count = dict()\n",
    "\n",
    "        def dfs(node: TreeNode | None) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ans = node.val\n",
    "            if node.left is not None:\n",
    "                ans += dfs(node.left)\n",
    "            if node.right is not None:\n",
    "                ans += dfs(node.right)\n",
    "            if ans not in ans_count:\n",
    "                ans_count[ans] = 1\n",
    "            else:\n",
    "                ans_count[ans] += 1\n",
    "            return ans\n",
    "\n",
    "        dfs(root)\n",
    "        _max = max(ans_count.values())\n",
    "        return [key for key in ans_count.keys() if ans_count[key] == _max]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "        self.sum = 0\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        \n",
    "        tmp = self.helper(root)\n",
    "        mav = 0\n",
    "        res = []\n",
    "        for key in self.map:\n",
    "            if self.map[key] > mav:\n",
    "                mav = self.map[key]\n",
    "        for key in self.map:\n",
    "            if self.map[key] == mav:\n",
    "                res.append(key)\n",
    "        return res\n",
    "\n",
    "    def helper(self, root):\n",
    "        if root:\n",
    "            sum1 = self.helper(root.left)\n",
    "            sum2 = self.helper(root.right)\n",
    "\n",
    "            sum0 = sum1 + sum2 + root.val\n",
    "            \n",
    "            self.map[sum0] = self.map.get(sum0, 0) + 1\n",
    "\n",
    "            return sum0\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return 0\n",
    "\n",
    "        cur = head.val + self.process(head.left) + self.process(head.right)\n",
    "        if cur in self.dic:\n",
    "            self.dic[cur] += 1\n",
    "        else:\n",
    "            self.dic[cur] = 1\n",
    "\n",
    "        if self.dic[cur] > self.maxn:\n",
    "            self.maxn = self.dic[cur]\n",
    "\n",
    "        return cur\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.maxn = -inf\n",
    "        self.dic = {}\n",
    "        results = []\n",
    "\n",
    "        self.process(root)\n",
    "        for i in self.dic.keys():\n",
    "            if self.dic[i] == self.maxn:\n",
    "                results.append(i)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        self.sum_dict = collections.defaultdict(int)\n",
    "        self.traverse(root)\n",
    "        maxCnt = max(self.sum_dict.values())\n",
    "        for k,v in self.sum_dict.items():\n",
    "            if v == maxCnt:\n",
    "                res.append(k)\n",
    "        return res\n",
    "\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.traverse(root.left)\n",
    "        right = self.traverse(root.right)\n",
    "        valsum = left + root.val + right\n",
    "        self.sum_dict[valsum] += 1\n",
    "        return valsum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def process(self, head):\n",
    "        if not head:\n",
    "            return 0\n",
    "\n",
    "        cur = head.val + self.process(head.left) + self.process(head.right)\n",
    "        if cur in self.dic:\n",
    "            self.dic[cur] += 1\n",
    "        else:\n",
    "            self.dic[cur] = 1\n",
    "\n",
    "        if self.dic[cur] > self.maxn:\n",
    "            self.maxn = self.dic[cur]\n",
    "\n",
    "        return cur\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.maxn = -inf\n",
    "        self.dic = {}\n",
    "        results = []\n",
    "\n",
    "        self.process(root)\n",
    "        for i in self.dic.keys():\n",
    "            if self.dic[i] == self.maxn:\n",
    "                results.append(i)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def traverse(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal max_count, res\n",
    "            l = traverse(node.left)\n",
    "            r = traverse(node.right)\n",
    "            cur = l + r + node.val \n",
    "            count[cur] += 1\n",
    "            if count[cur] > max_count:\n",
    "                res = [cur]\n",
    "                max_count = count[cur]\n",
    "            elif count[cur] == max_count:\n",
    "                res.append(cur)\n",
    "            return cur \n",
    "        \n",
    "        res = []\n",
    "        max_count = 0\n",
    "        count = Counter()\n",
    "        traverse(root)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.sum_count_dict = {}\n",
    "        self.traversal(root)\n",
    "        \n",
    "        max_count = 0\n",
    "        for count in self.sum_count_dict.values():\n",
    "            max_count = max(max_count,count)\n",
    "        res = []\n",
    "        for key in self.sum_count_dict.keys():\n",
    "            if  self.sum_count_dict[key] == max_count:\n",
    "                res.append(key)\n",
    "        arr = [x for x in res]\n",
    "\n",
    "        return arr\n",
    "\n",
    "    def traversal(self,root):\n",
    "        # 定义：输入一个节点，返回以该节点为根的二叉树所有节点之和\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_sum = self.traversal(root.left)\n",
    "        right_sum = self.traversal(root.right)\n",
    "        res = root.val+left_sum+right_sum\n",
    "        self.sum_count_dict[res] = self.sum_count_dict.get(res, 0) + 1      \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum_count = {}\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.sum(root)\n",
    "        max_count = max(self.sum_count.values())\n",
    "        return [treesum for treesum, count in self.sum_count.items() if count == max_count]\n",
    "\n",
    "    def sum(self, root: TreeNode):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left = self.sum(root.left)\n",
    "        right = self.sum(root.right)\n",
    "        treesum = left + right + root.val\n",
    "        self.sum_count[treesum] = self.sum_count.get(treesum, 0) + 1\n",
    "        return treesum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.get_sum(root)\n",
    "        count = {}\n",
    "        max_count = 0\n",
    "        count, max_count = self.search(root, count, max_count)\n",
    "        ans = []\n",
    "        for i in count:\n",
    "            if count[i] == max_count:\n",
    "                ans.append(i)\n",
    "        return ans\n",
    "\n",
    "    def get_sum(self, root):\n",
    "        if root.left != None and root.right == None:\n",
    "            self.get_sum(root.left)\n",
    "            root.val += root.left.val\n",
    "        elif root.left == None and root.right != None:\n",
    "            self.get_sum(root.right)\n",
    "            root.val += root.right.val\n",
    "        elif root.left != None and root.right != None:\n",
    "            self.get_sum(root.left)\n",
    "            self.get_sum(root.right)\n",
    "            root.val += root.left.val + root.right.val\n",
    "\n",
    "    def search(self, root, count, max_count):\n",
    "        if root.val in count:\n",
    "            count[root.val] += 1\n",
    "        else:\n",
    "            count[root.val] = 1\n",
    "        if count[root.val] > max_count:\n",
    "            max_count = count[root.val]\n",
    "        if root.left != None:\n",
    "            count, max_count = self.search(root.left, count, max_count)\n",
    "        if root.right != None:\n",
    "            count, max_count = self.search(root.right, count, max_count)\n",
    "        return count, max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def Treesum(self, root: Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.Treesum(root.left)+self.Treesum(root.right)+root.val\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return None\n",
    "        ans=defaultdict(int)\n",
    "        queue=collections.deque([root])\n",
    "        while queue:\n",
    "            node=queue.popleft()\n",
    "            if node:\n",
    "                ans[self.Treesum(node)]+=1\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        maxsum=max(ans.values())\n",
    "        return [key for key , value in ans.items() if value==maxsum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "\r\n",
    "\r\n",
    "def traceTree(root: Optional[TreeNode], counter: dict()):\r\n",
    "    \r\n",
    "    if root is None:\r\n",
    "        return 0\r\n",
    "        \r\n",
    "    left = traceTree(root.left, counter)\r\n",
    "    \r\n",
    "    right = traceTree(root.right, counter)\r\n",
    "    \r\n",
    "    val = root.val\r\n",
    "    \r\n",
    "    total = left + right + val\r\n",
    "    \r\n",
    "    if total not in counter:\r\n",
    "        counter[total] = 1\r\n",
    "    else:\r\n",
    "        counter[total] += 1\r\n",
    "    \r\n",
    "    return total\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\r\n",
    "        res = []\r\n",
    "        max_sum = 0\r\n",
    "        counter = dict()\r\n",
    "        \r\n",
    "        \r\n",
    "        traceTree(root, counter)\r\n",
    "        \r\n",
    "        for item in counter.keys():\r\n",
    "            max_sum = max(counter[item], max_sum)\r\n",
    "        \r\n",
    "        for item in counter.keys():\r\n",
    "            if counter[item] == max_sum:\r\n",
    "                res.append(item)\r\n",
    "        \r\n",
    "        return res\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        \n",
    "        cnt = {}\n",
    "        def process(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            \n",
    "            v = node.val\n",
    "            v += process(node.left)\n",
    "            v += process(node.right)\n",
    "\n",
    "            cnt[v] = cnt.get(v, 0) + 1\n",
    "            return v\n",
    "        \n",
    "        process(root)\n",
    "\n",
    "        maxv = max(cnt.values())\n",
    "\n",
    "        return [k for k, v in cnt.items() if v == maxv]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        cnt = Counter()\n",
    "\n",
    "        def dfs(node: TreeNode) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            sum = node.val + dfs(node.left) + dfs(node.right)\n",
    "            cnt[sum] += 1\n",
    "            return sum\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        maxCnt = max(cnt.values())\n",
    "        return [s for s, c in cnt.items() if c == maxCnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: TreeNode) -> List[int]:\n",
    "        cnt = Counter()\n",
    "        def dfs(node: TreeNode) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            sum = node.val + dfs(node.left) + dfs(node.right)\n",
    "            cnt[sum] += 1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "\n",
    "        maxCnt = max(cnt.values())\n",
    "        return [s for s, c in cnt.items() if c == maxCnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        p = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                p[node.val] += 1\n",
    "                return node.val\n",
    "            \n",
    "            p[(res:=dfs(node.left)+node.val+dfs(node.right))] += 1\n",
    "            return res\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        _max = max(p.values())\n",
    "        return [k for k,v in p.items() if v == _max]\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = Counter()\n",
    "        def dfs(root):\n",
    "\n",
    "            if root is None:\n",
    "                return 0\n",
    "            sum = root.val + dfs(root.left) + dfs(root.right)\n",
    "            res[sum] += 1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "        maxCnt = max(res.values())\n",
    "        return [s for s, c in res.items() if c == maxCnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        count_dict = defaultdict(int)\n",
    "        def dfs(node:TreeNode):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            left_sum = dfs(node.left)\n",
    "            rigth_sum = dfs(node.right)\n",
    "\n",
    "            count_dict[left_sum + rigth_sum + node.val] += 1\n",
    "            return left_sum + rigth_sum + node.val\n",
    "        \n",
    "        dfs(root)\n",
    "        return [x for x in count_dict.keys() if count_dict[x] == max(count_dict.values())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root:TreeNode):\n",
    "        recode = dict()\n",
    "        \n",
    "        def dfs(root:TreeNode):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            sums = root.val + dfs(root.left) + dfs(root.right)\n",
    "            if sums in recode:\n",
    "                recode[sums] += 1\n",
    "            else:\n",
    "                recode[sums] = 1\n",
    "            return sums\n",
    "        dfs(root)\n",
    "        return [key for key in recode.keys() if recode[key] == max(recode.values())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ### 对每一颗子树算它的元素和\n",
    "        cnt = Counter()\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            left=dfs(root.left)\n",
    "            right=dfs(root.right)\n",
    "            sum=left+right+root.val\n",
    "            cnt[sum]+=1\n",
    "            return sum\n",
    "\n",
    "        dfs(root)\n",
    "        max_res=max(cnt.values())\n",
    "        return [s for s,c in cnt.items() if c==max_res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(node):\n",
    "            l = dfs(node.left) if node.left else 0\n",
    "            r = dfs(node.right) if node.right else 0\n",
    "            s = node.val + l + r\n",
    "            d[s] = d.get(s, 0) + 1\n",
    "            return s\n",
    "        \n",
    "        d={}\n",
    "        dfs(root)\n",
    "        return [i for i,j in d.items() if j==max(d.values())]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        recode = dict()\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            sum = root.val + dfs(root.left)+dfs(root.right)\n",
    "            if sum in recode:\n",
    "                recode[sum] += 1\n",
    "            else:\n",
    "                recode[sum] = 1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "        max_count = max(recode.values())\n",
    "        return [key for key,val in recode.items() if val == max_count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root:TreeNode):\n",
    "        recode = dict()\n",
    "        \n",
    "        def dfs(root:TreeNode):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            sums = root.val + dfs(root.left) + dfs(root.right)\n",
    "            if sums in recode:\n",
    "                recode[sums] += 1\n",
    "            else:\n",
    "                recode[sums] = 1\n",
    "            return sums\n",
    "        dfs(root)\n",
    "        max_count = max(recode.values())\n",
    "        return [key for key,val in recode.items() if val == max_count]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        cnts = Counter()\n",
    "        def dfs(node: TreeNode) -> int:\n",
    "            if node:\n",
    "                left, right = dfs(node.left), dfs(node.right)\n",
    "                cnts[node.val + left + right] += 1\n",
    "                return node.val + left + right\n",
    "            return 0\n",
    "        dfs(root)\n",
    "        most = max(cnts.values())\n",
    "        return [k for k, v in cnts.items() if v == most]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        cnt = Counter()\n",
    "        def dfs(node: TreeNode) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            sum = node.val + dfs(node.left) + dfs(node.right)\n",
    "            cnt[sum] += 1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "\n",
    "        maxCnt = max(cnt.values())\n",
    "        return [s for s, c in cnt.items() if c == maxCnt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def dfs(root):\n",
    "            nonlocal maxnum\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0\n",
    "            num = dfs(root.left) + dfs(root.right) + root.val\n",
    "            count[num] += 1\n",
    "            if count[num] > maxnum:\n",
    "                maxnum = count[num]\n",
    "                res = set([num])\n",
    "            elif count[num] == maxnum:\n",
    "                res.add(num)\n",
    "            return num\n",
    "        maxnum = 0\n",
    "        count = collections.defaultdict(int)\n",
    "        res = set()\n",
    "        dfs(root)\n",
    "        return list(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        cnt=Counter()\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            sum = node.val + dfs(node.left) + dfs(node.right)\n",
    "            cnt[sum]+=1\n",
    "            return sum\n",
    "        dfs(root)\n",
    "        maxcnt = max(cnt.values())\n",
    "        return [s for s , t in cnt.items() if t==maxcnt]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        h = defaultdict(int)\n",
    "        def dfs(root):\n",
    "            res = root.val\n",
    "            if root.right:\n",
    "                res += dfs(root.right)\n",
    "            if root.left:\n",
    "                res += dfs(root.left)\n",
    "            h[res] += 1\n",
    "            return res\n",
    "        dfs(root)\n",
    "        ma = max(h.values())\n",
    "        return [k for k, v in h.items() if v == ma]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res=[]\n",
    "        sumdic=collections.defaultdict(int)\n",
    "        def dfs(node:TreeNode)->int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            #求元素和,左子树和，右子树和，根节点值\n",
    "            sumall=dfs(node.left)+dfs(node.right)+node.val\n",
    "            #统计每个节点‘子树元素和’出现频率，返回出现频次最多的‘子树元素和’\n",
    "            sumdic[sumall]+=1\n",
    "            return sumall\n",
    "        dfs(root)\n",
    "        #求最大值出现最多的\n",
    "        maxcount=max(sumdic.values())\n",
    "        for k,v in sumdic.items():\n",
    "        #遍历哈希表，出现最多的对应的key('元素和')加入结果\n",
    "            if v==maxcount:\n",
    "                res.append(k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        m=collections.defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if root!=None:\n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "                if root.left!=None:\n",
    "                    root.val=root.val+root.left.val\n",
    "                if root.right!=None:\n",
    "                    root.val=root.val+root.right.val\n",
    "                m[root.val]+=1\n",
    "        dfs(root)\n",
    "        sorted_list = sorted(m.items(), key=lambda x: x[1],reverse=True)\n",
    "\n",
    "        # 遍历排序后的列表，输出每一项\n",
    "        m=sorted_list[0][1]\n",
    "        m1=[]\n",
    "        m1.append(sorted_list[0][0])\n",
    "        for item in sorted_list[1:]:\n",
    "            if m==item[1]:\n",
    "                m1.append(item[0])\n",
    "        return m1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        # dfs负责统计每个子树的和\n",
    "        val = collections.defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            nonlocal val\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            res = root.val + left + right\n",
    "            val[res] += 1\n",
    "            return res\n",
    "        dfs(root)\n",
    "        maxcnt = max(val.values())\n",
    "        res = []\n",
    "        for key in val.keys():\n",
    "            if val[key] == maxcnt:\n",
    "                res.append(key)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root):\n",
    "        # base \n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        count=collections.Counter()\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            \n",
    "            curr_res=node.val+dfs(node.left)+dfs(node.right)\n",
    "            count[curr_res]+=1\n",
    "            return curr_res\n",
    "        \n",
    "        dfs(root)\n",
    "        max_val=max(count.values())\n",
    "        return [s for s in count if count[s]==max_val]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            tmp = root.val + dfs(root.left) + dfs(root.right)\n",
    "            ans[tmp] += 1\n",
    "            return tmp\n",
    "        dfs(root)\n",
    "        res = sorted(ans.keys(), key = lambda x: ans[x], reverse = True)\n",
    "        ret = [res[0]]\n",
    "        for i in range(1, len(res)):\n",
    "            if ans[res[i]] == ans[ret[-1]]:\n",
    "                ret.append(res[i])\n",
    "            else:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.di = dict()\n",
    "        self.res = []\n",
    "        self.max_cnt = 0\n",
    "        def dfs(node):\n",
    "            v = node.val\n",
    "            if node.left:\n",
    "                v += dfs(node.left)\n",
    "            if node.right:\n",
    "                v += dfs(node.right)\n",
    "            self.di[v] = self.di.get(v, 0) + 1\n",
    "            if self.di[v] > self.max_cnt:\n",
    "                self.res = [v]\n",
    "                self.max_cnt = self.di[v]\n",
    "            elif self.di[v] == self.max_cnt:\n",
    "                self.res.append(v)\n",
    "            return v\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        dict1 = []\n",
    "        def Sumres(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            leftRes = Sumres(root.left)\n",
    "            rightRes = Sumres(root.right)\n",
    "            dict1.append(root.val+leftRes+rightRes)\n",
    "            return root.val+ leftRes + rightRes\n",
    "        Sumres(root)\n",
    "        res = collections.Counter(dict1)\n",
    "        maxCnt = max(res.values())\n",
    "        print(maxCnt)\n",
    "        resfin=[]\n",
    "        for s,c in res.items():\n",
    "            print(s,c)\n",
    "            if c == maxCnt:\n",
    "                resfin.append(s)\n",
    "        return resfin\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        dic=defaultdict(int)\n",
    "        def dfs(root):\n",
    "            nonlocal dic\n",
    "            if not root:\n",
    "                return 0\n",
    "            leftsum=dfs(root.left)\n",
    "            rightsum=dfs(root.right)\n",
    "            treesum=root.val+leftsum+rightsum\n",
    "            dic[treesum]+=1\n",
    "            return treesum\n",
    "        dfs(root)\n",
    "        maxfre=max(dic.values(),default=0)\n",
    "        return [key for key,value in dic.items() if value==maxfre]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        freq = defaultdict(int)\n",
    "\n",
    "        def walk(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            left = walk(node.left)\n",
    "            right = walk(node.right)\n",
    "            val = node.val + left + right\n",
    "            freq[val] += 1\n",
    "            return val\n",
    "\n",
    "        walk(root)\n",
    "        maxfreq = max(freq.values())\n",
    "\n",
    "        res = []\n",
    "        for k, v in freq.items():\n",
    "            if v == maxfreq:\n",
    "                res.append(k)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class Solution:\r\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\r\n",
    "        counter={}\r\n",
    "        max_cnt=0\r\n",
    "        ret=[]\r\n",
    "        def calc(root:TreeNode):\r\n",
    "            nonlocal max_cnt,ret,counter\r\n",
    "            if not root:\r\n",
    "                return 0\r\n",
    "            s=root.val+calc(root.left)+calc(root.right)\r\n",
    "            cnt=counter.get(s,0)+1\r\n",
    "            counter[s]=cnt\r\n",
    "            if cnt>max_cnt:\r\n",
    "                ret=[s]\r\n",
    "                max_cnt=cnt\r\n",
    "            elif cnt==max_cnt:\r\n",
    "                ret.append(s)\r\n",
    "            return s\r\n",
    "        calc(root)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        cnt = defaultdict(int)\n",
    "        mm = sys.maxsize\n",
    "        flag = {}\n",
    "        def dfs(r):\n",
    "            if not r:\n",
    "                return mm\n",
    "            if flag.get(r) is not None:\n",
    "                return flag[r]\n",
    "            lv, rv = dfs(r.left), dfs(r.right)\n",
    "            v = sum([r.val, 0 if lv == mm else lv, 0 if rv == mm else rv])\n",
    "            cnt[v] += 1\n",
    "            flag[r] = v\n",
    "            return v\n",
    "        dfs(root)\n",
    "        res = [0, []]\n",
    "        for k, v in cnt.items():\n",
    "            if v > res[0]:\n",
    "                res = [v, [k]]\n",
    "            elif v == res[0]:\n",
    "                res[1].append(k)\n",
    "        return res[1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        from collections import defaultdict\n",
    "\n",
    "        nodesums = defaultdict(int) \n",
    "\n",
    "        def dfs(node) -> int:\n",
    "            cur = node.val \n",
    "            if node.left:\n",
    "                cur += dfs(node.left)\n",
    "            if node.right:\n",
    "                cur += dfs(node.right)\n",
    "            nodesums[cur] += 1\n",
    "            return cur\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        max_value = max(nodesums.values())\n",
    "        \n",
    "        return [k for k in nodesums.keys() if nodesums[k] == max_value]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        setattr(TreeNode, \"sum\", 0)\n",
    "        def gen(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left = gen(root.left)\n",
    "            right = gen(root.right)\n",
    "            root.sum = left + right + root.val\n",
    "            return root.sum\n",
    "        \n",
    "        m = {}\n",
    "        def count(root, m):\n",
    "            if root is None:\n",
    "                return\n",
    "            m[root.sum] = m.get(root.sum, 0) + 1\n",
    "            count(root.left, m)\n",
    "            count(root.right, m)\n",
    "        \n",
    "        gen(root)\n",
    "        count(root, m)\n",
    "\n",
    "        x = sorted(m.items(), key=lambda x:x[1])\n",
    "        max_cnt = x[-1][1]\n",
    "        ans = []\n",
    "        for k, v in m.items():\n",
    "            if v == max_cnt:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        dic = defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            else:\n",
    "                ans = dfs(root.left) + dfs(root.right) + root.val\n",
    "                dic[ans] += 1\n",
    "                return ans\n",
    "        \n",
    "        dfs(root)\n",
    "        dic = dict(dic)\n",
    "        ans = sorted(dic.keys(), key = lambda x: dic[x], reverse = True)\n",
    "        ans_final = []\n",
    "        for k in ans:\n",
    "            if dic[k] == dic[ans[0]]:\n",
    "                ans_final.append(k)\n",
    "        return ans_final\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        record = defaultdict(int)\n",
    "\n",
    "        def dfs(r):\n",
    "            val = r.val\n",
    "            if r.left is not None:\n",
    "                val += dfs(r.left)\n",
    "\n",
    "            if r.right is not None:\n",
    "                val += dfs(r.right)\n",
    "            record[val] += 1\n",
    "            return val\n",
    "\n",
    "        dfs(root)\n",
    "        res = []\n",
    "        for key in record:\n",
    "            res.append((-record[key], key))\n",
    "\n",
    "        heapq.heapify(res)\n",
    "        maxfreq, item = heapq.heappop(res)\n",
    "        ans = [item]\n",
    "        if not res:\n",
    "            return ans\n",
    "        freq, i = heapq.heappop(res)\n",
    "        while freq == maxfreq:\n",
    "            ans.append(i)\n",
    "            if res:\n",
    "                freq, i = heapq.heappop(res)\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.sums = {}\n",
    "        self.dfs(root)\n",
    "\n",
    "        result = []\n",
    "        maxCount = 0\n",
    "        d = {}\n",
    "        for total in self.sums.values():\n",
    "            if not total in d:\n",
    "                d[total] = 1\n",
    "            else:\n",
    "                d[total] += 1\n",
    "            \n",
    "            if d[total] > maxCount:\n",
    "                maxCount = d[total]\n",
    "                result = [total]\n",
    "            elif d[total] == maxCount:\n",
    "                result.append(total)\n",
    "        return result\n",
    "        \n",
    "    def dfs(self, node: TreeNode):\n",
    "        if not node:\n",
    "            return 0\n",
    "\n",
    "        key = id(node)\n",
    "        if key in self.sums:\n",
    "            return self.sums[key]\n",
    "\n",
    "        L = self.dfs(node.left)\n",
    "        R = self.dfs(node.right)\n",
    "        n = L + R + node.val\n",
    "        self.sums[key] = n\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def find_node(self, node, sum_l):\n",
    "        if node.left:\n",
    "            left_val = self.find_node(node.left, sum_l)\n",
    "        if node.right:\n",
    "            right_val = self.find_node(node.right, sum_l)\n",
    "        if node.left and node.right:\n",
    "            tem = left_val + right_val + node.val\n",
    "            sum_l.append(tem)\n",
    "            return tem\n",
    "        elif node.left:\n",
    "            tem = left_val + node.val\n",
    "            sum_l.append(tem)\n",
    "            return tem\n",
    "        elif node.right:\n",
    "            tem = right_val + node.val\n",
    "            sum_l.append(tem)\n",
    "            return tem\n",
    "        else:\n",
    "            sum_l.append(node.val)\n",
    "            return node.val\n",
    "\n",
    "\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        sum_l = []\n",
    "        self.find_node(root, sum_l)\n",
    "        d = Counter(sum_l)\n",
    "        l = sorted(d.items(), key=lambda x:-x[1])\n",
    "        ans = [l[0][0]]\n",
    "        for i in l[1:]:\n",
    "            if i[1] == l[0][1]:\n",
    "                ans.append(i[0])\n",
    "            else:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans=[]\n",
    "        if not root:\n",
    "            return ans\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                ans.append(root.val)\n",
    "                return root.val\n",
    "            sm=root.val\n",
    "            if root.left:\n",
    "                sm+=dfs(root.left)\n",
    "            if root.right:\n",
    "                sm+=dfs(root.right)\n",
    "            ans.append(sm)\n",
    "            return sm\n",
    "        dfs(root)\n",
    "        B=collections.Counter(ans)\n",
    "        m=0\n",
    "        for k,y in B.most_common():\n",
    "            m=max(m,y)\n",
    "        res=[]\n",
    "        for k,y in B.most_common():\n",
    "            if y==m:\n",
    "                res.append(k)\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from typing import Optional, List\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def isLeaf(node: TreeNode):\n",
    "            if node.left is None and node.right is None:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        def traversal(node: TreeNode) -> int:\n",
    "            if isLeaf(node):\n",
    "                return node.val\n",
    "            else:\n",
    "                node.val += (0 if node.left is None else traversal(node.left)) + (\n",
    "                    0 if node.right is None else traversal(node.right))\n",
    "                return node.val\n",
    "\n",
    "        traversal(root)\n",
    "        dic = {}\n",
    "\n",
    "        def statistic(node: TreeNode):\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val not in dic.keys():\n",
    "                dic[node.val] = 1\n",
    "            else:\n",
    "                dic[node.val] += 1\n",
    "            statistic(node.left)\n",
    "            statistic(node.right)\n",
    "\n",
    "        statistic(root)\n",
    "        count_map = sorted(dic.items(), key=lambda d: d[1], reverse=True)\n",
    "        max_count = count_map[0][1]\n",
    "        ans = []\n",
    "        for item in count_map:\n",
    "            if item[1] != max_count:\n",
    "                break\n",
    "            ans.append(item[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ops = []\n",
    "        def dfs(x):\n",
    "            if not x.left and not x.right:\n",
    "                ops.append(x.val)\n",
    "                return x.val\n",
    "            l = dfs(x.left) if x.left else 0\n",
    "            r = dfs(x.right) if x.right else 0\n",
    "            cur = x.val+l+r\n",
    "            ops.append(cur)\n",
    "            return cur\n",
    "        dfs(root)\n",
    "        c = Counter(ops).most_common()\n",
    "        freq = c[0][1]\n",
    "        return [x for (x,y) in c if y == freq]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        my_dict=Counter()\n",
    "        def f(root):\n",
    "            if root==None:\n",
    "                return 0\n",
    "            this_sum=root.val\n",
    "            this_sum+=f(root.left)\n",
    "            this_sum+=f(root.right)\n",
    "            nonlocal my_dict\n",
    "            my_dict[this_sum]+=1\n",
    "            return this_sum\n",
    "        f(root)\n",
    "        my_dict=sorted(my_dict.items(),key=lambda x:-x[1])\n",
    "        ret=[]\n",
    "        last=my_dict[0][1]\n",
    "        i=0\n",
    "        while i<len(my_dict) and my_dict[i][1]==last:\n",
    "            ret.append(my_dict[i][0])\n",
    "            i+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        dic = {}\n",
    "        def postOrder(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            sum_left = postOrder(root.left)\n",
    "            sum_rigt = postOrder(root.right)\n",
    "            sum_tree = sum_left + sum_rigt + root.val\n",
    "            if sum_tree in dic:\n",
    "                dic[sum_tree] += 1\n",
    "            else:\n",
    "                dic[sum_tree] = 1\n",
    "            return sum_tree\n",
    "        postOrder(root)\n",
    "        dic = sorted(dic.items(),key = lambda x:-x[1])\n",
    "        res = []\n",
    "        for k,v in dic:\n",
    "            if v != dic[0][1]:\n",
    "                break\n",
    "            res.append(k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        self.sums = {}\n",
    "        self.dfs(root)\n",
    "\n",
    "        result = []\n",
    "        maxCount = 0\n",
    "        d = {}\n",
    "        for n in self.sums.values():\n",
    "            if not n in d:\n",
    "                d[n] = 1\n",
    "            else:\n",
    "                d[n] += 1\n",
    "            \n",
    "            if d[n] > maxCount:\n",
    "                maxCount = d[n]\n",
    "                result = [n]\n",
    "            elif d[n] == maxCount:\n",
    "                result.append(n)\n",
    "        return result\n",
    "        \n",
    "    def dfs(self, node: TreeNode):\n",
    "        if not node:\n",
    "            return 0\n",
    "\n",
    "        k = id(node)\n",
    "        if k in self.sums:\n",
    "            #print(k, 'exists')\n",
    "            return self.sums[k]\n",
    "\n",
    "        L = self.dfs(node.left)\n",
    "        R = self.dfs(node.right)\n",
    "        n = L + R + node.val\n",
    "        self.sums[k] = n\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node:Optional[TreeNode]) -> int:  # 返回当前结点的子树元素和\n",
    "            if not node:  # 回溯\n",
    "                return 0\n",
    "            l_sum = dfs(node.left)  # 递左子树元素和\n",
    "            r_sum = dfs(node.right)  # 递右子树元素和\n",
    "            node_sum = l_sum + r_sum + node.val\n",
    "            nonlocal ans\n",
    "            ans.append(node_sum)\n",
    "            return node_sum\n",
    "        dfs(root)\n",
    "        # 统计子树元素和出现次数，并按出现次数进行排序,\n",
    "        dic = dict(sorted(dict(Counter(ans)).items(), key=lambda x:x[1]))\n",
    "        ans.clear()\n",
    "        for k, v in dic.items():\n",
    "            # 如果value值（次数）等于最高次数，就将其对应的子树元素和k添加到ans中\n",
    "            if v == dic[list(dic)[-1]]:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node:Optional[TreeNode]) -> int:  # 返回当前结点的子树元素和\n",
    "            if not node:  # 回溯\n",
    "                return 0\n",
    "            l_sum = dfs(node.left)  # 递左子树元素和\n",
    "            r_sum = dfs(node.right)  # 递右子树元素和\n",
    "            node_sum = l_sum + r_sum + node.val\n",
    "            nonlocal ans\n",
    "            ans.append(node_sum)\n",
    "            return node_sum\n",
    "        dfs(root)\n",
    "        # 统计子树元素和出现次数，并按出现次数进行排序,\n",
    "        dic = dict(sorted(dict(Counter(ans)).items(), key=lambda x:x[1]))\n",
    "        ans.clear()\n",
    "        for k, v in dic.items():\n",
    "            # 如果value值（次数）等于最高次数，就将其对应的子树元素和k添加到ans中\n",
    "            if v == dic[list(dic)[-1]]:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "\n",
    "        d = {}\n",
    "\n",
    "        def search(root):\n",
    "            nonlocal d \n",
    "\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            # print(root.val)\n",
    "\n",
    "            res = search(root.left) + search(root.right) + root.val\n",
    "\n",
    "            if res not in d:\n",
    "                d[res] = 0\n",
    "            else:\n",
    "                d[res] += 1\n",
    "\n",
    "            return res\n",
    "        search(root)\n",
    "        sorted_d = sorted(d.items(),key = lambda x:x[1],reverse = True)\n",
    "        # print(d)\n",
    "        # print(sorted_d)\n",
    "        max_ = sorted_d[0][1]\n",
    "        res = []\n",
    "        for a,b in sorted_d:\n",
    "            if b == max_:\n",
    "                res.append(a)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans = []\n",
    "        def dfs(node:Optional[TreeNode]) -> int:  # 返回当前结点的子树元素和\n",
    "            if not node:  # 回溯\n",
    "                return 0\n",
    "            l_sum = dfs(node.left)  # 递左子树元素和\n",
    "            r_sum = dfs(node.right)  # 递右子树元素和\n",
    "            node_sum = l_sum + r_sum + node.val\n",
    "            nonlocal ans\n",
    "            ans.append(node_sum)\n",
    "            return node_sum\n",
    "        dfs(root)\n",
    "        # 统计子树元素和出现次数，并按出现次数进行排序,\n",
    "        dic = dict(sorted(dict(Counter(ans)).items(), key=lambda x:x[1]))\n",
    "        ans.clear()\n",
    "        for k, v in dic.items():\n",
    "            # 如果value值（次数）等于最高次数，就将其对应的子树元素和k添加到ans中\n",
    "            if v == dic[list(dic)[-1]]:\n",
    "                ans.append(k)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
